Traditionally, computer graphics systems have involved the display of data on the screen of a cathode ray tube (CRT) to accomplish dynamic images. Typically, the displays are composed by a rectangular array including thousands of individual picture elements (pixels or pels). Each pixel is represented by specific stored pixel data, for example data representing color, intensity and depth.
Pixel data may be supplied to the CRT from a so called "frame buffer" capable of providing and delivering the data at a high rate. Various formats for organizing frame buffers to drive displays are disclosed in a textbook entitled "Computer Graphics: Principles and Practice", Second Edition, Foley, Van Dam, Feiner and Hughes, published 1987, by Addison-Wesley Publishing Company (incorporated herein by reference).
To sequentially "display" or "write", pixels by exciting the CRT display screen, raster-scan patterns are widely used, both in television and in the field of computer graphics. Raster scan operation can be analogized to the pattern of western reading, i.e. pixels, like words are scanned one by one, from left to right, row by row, moving downward. Thus, the exciting beam in a CRT traces a raster pattern to accomplish a dynamic display pixel-by-pixel, line-by-line, frame-by-frame. The system for such a display typically includes a central processor unit, a system bus, a main memory, a frame buffer, a video controller and a CRT display unit. Such systems are described in detail in the above-referenced Foley textbook.
Generally, to support a dynamic graphics display, three-dimensional geometric data, representative of objects or primitives (e.g. polygons, as triangles), is stored in the main memory. The geometric data is processed to provide selected data that is scan converted to generate display data defining each individual pixel. The resulting data is stored in the frame buffer and supplied to drive the CRT display in raster sequence. Typically, for dynamic displays, the frame buffer is cyclically refreshed or loaded during first intervals preparatory to driving the display during alternating second intervals.
For a raster scan display, convention has involved organizing the processing sequence to load the frame buffer in a sequence relationship similar to the raster pattern. That is, the raster scanline organization of frame buffers for delivering video data to the CRT, usually has been duplicated for writing-pixel data into the frame buffer. Usually, data is scan converted to develop and store pixels in fragments of the raster sequence. To some extent, particularly in view of certain storage devices, the technique sometimes improved access to data for processing.
At this point, a few comments are deemed appropriate on the scan conversion of data to provide individual pixels. Essentially, graphics images are formed from primitive shapes (typically triangles) defining objects that appear in the display. To generate the pixels, the selected primitives are dissected by scan conversion to determine contributions to each pixel in the display. As the primitives are processed, the dominance of objects is resolved. For example, a dominant object may hide surfaces of another object. Accordingly, primitives are considered individually in relation to the cumulative determinations of each pixel (stored in the frame buffer) until all objects are considered. Concurrent with the processing of primitives, textures also can be reflected in the pixels from a texture memory.
Generally, the performance of a video graphics system is controlled by several factors as discussed in the above-identified Foley textbook, specifically in a section beginning on page 882. Three significant factors are: (1) the speed at which pixels can be generated by a processor or scanning engine, (2) the speed at which resultant pixels can be written into a frame buffer, and (3) when images are mapped with texture, the speed at which the texture elements (texels) can be read from a texture memory. A detailed treatment of the problems attendant memory operation for graphics systems is presented in an article entitled "Memory Design for Raster Graphics Displays" by Mary C. Whitton, published in IEEE CG&A, in 1984 designated 0272-1716/84/0300-0048 (incorporated herein by reference).
The speed of generating pixels in a scanning engine or processor has traditionally been faster than the ability of a system to either: read texels from a texture memory for texture mapping, or write resultant pixels into a frame buffer memory. To help alleviate this memory bandwidth problem, systems have been built with multiple banks of texture memory and/or frame buffer memory. The several banks can operate in parallel at slower memory speeds, so that any one bank of memory need not run at the speed of the pixel-scanning engine. However, as a group, the combined memory banks match the speed of the engine. In that regard, various parallel frame buffer organizations have been proposed, including the examples disclosed in the above-referenced Foley textbook at pages 887 and 890-893. Still, a need continues to exist for an improved system to scan primitives (dots, lines, polygons, or other surfaces) to generate pixels and store them in a frame buffer.
Generally, in accordance herewith, instead of scan processing a primitive in the traditional scanline order, distinct areas of the primitives are scanned in order. By scanning select primitive areas, the generated pixels can coincide to the needs of a particular frame buffer organization. Also by scanning select primitive areas in order, texture memory may be accessed in a relatively fast cache mode.
Essentially as disclosed herein, a multiple-level scanning approach is utilized to scan process primitives. For example, in relation to a display screen, defined span areas may constitute four-by-four pixel arrays and the pixels of a span (within a primitive or polygon) are generated in sequence. If a span is only partly covered by a polygon, only those pixels within the polygon (or contributing, as from a borderline location) are generated. After scanning the select pixels within a span, the system proceeds to scan another span. Spans may be of various configurations, e.g. square, rectangular, and they may include varying numbers of pixels.
Structurally, the system of the present invention may be embodied in accordance with various architectures for accomplishing computer displays. In that regard, a front end portion of the system may traverse data, transforming select primitives into screen space. Processing the primitives in screen space, a backend or scan processing portion then creates pixels for the final image. That is, by scan converting each primitive, the backend portion of the system identifies the contribution of primitives to each pixel and provides the appropriate shading. In the disclosed embodiment, a multi-level scan conversion sequence is used to generate pixels. Texture mapping is performed in the scan conversion and multiple rendering processors may be employed.
Recapitulating to some extent, the present invention may be implemented in a graphics system utilizing a geometric processor (front end) to provide primitives in screen space as in the form of polygons, e.g. triangles. A rendering or backend processor then scan converts the primitives utilizing a multi-level approach. In terms of two-dimensional screen space, span areas (spans) define arrays of pixels in relation to primitives. Portions of spans within primitives are scan converted, pixel-by-pixel in the processing of each span. After scan processing the appropriate pixels within each span, the system proceeds to scan another span.
Further in accordance herewith, a texture memory may be employed to store a texture map image for application to a polygon. Note that the texture memory is optional and is only required in systems performing texture mapping. In any event, as polygons are scan processed, the frame buffer receives and stores the resulting pixel data. In accordance herewith, for both a texture memory and the frame buffer, small, very fast cache memories may be utilized. In that regard, basic cache memories are well known and have been widely utilized.
In an alternative embodiment, a form of three-level scanning is disclosed. The lowest level involves scanning pixels within a span area (e.g. two-by-two or four-by-four pixels). The intermediate level of scanning is the spans within a panel area (e.g. 8.times.8 or 16.times.16 spans). Finally, all panels within a primitive area are scanned, that is, those panels containing pixels that may be affected by the primitive.
Generally, three-level scanning has been found particularly useful when higher level performance is desired by using multiple rendering processors operating in parallel. Such an embodiment also is disclosed. In that regard, each processor is assigned specific panels to scan. Within a panel, the processor generates pixels for all span areas within the panel and the primitive. After completing a panel, a processor begins generating pixels for some other panel. For example, eight rendering processors might be employed to simultaneously compute pixels for eight different panels.